\contentsline {chapter}{\numberline {1}Introduction}{1}
\contentsline {paragraph}{Organization of the Thesis}{7}
\contentsline {chapter}{\numberline {2}Shared Memory Architectures}{9}
\contentsline {section}{\numberline {2.1}Processing Nodes}{11}
\contentsline {section}{\numberline {2.2}Interconnection Structures}{14}
\contentsline {subsection}{\numberline {2.2.1}Base Latency in Networks with Wormhole Flow Control}{16}
\contentsline {subsection}{\numberline {2.2.2}Base Latency in Time-Slot Networks on chip}{17}
\contentsline {subsection}{\numberline {2.2.3}Direct and Indirect Interconnection Structures}{18}
\contentsline {section}{\numberline {2.3}Shared Memory}{20}
\contentsline {subsection}{\numberline {2.3.1}UMA and NUMA Architectures}{22}
\contentsline {subsection}{\numberline {2.3.2}Base and Under-Load Memory Access Latency}{24}
\contentsline {section}{\numberline {2.4}Synchronization and Cache Coherence}{24}
\contentsline {section}{\numberline {2.5}Cost Model and Abstract Architecture}{27}
\contentsline {chapter}{\numberline {3}Queueing Theory Concepts}{31}
\contentsline {section}{\numberline {3.1}Description and Characterization of a Queue}{31}
\contentsline {paragraph}{Description of Queues}{31}
\contentsline {paragraph}{Inter-departures Process}{33}
\contentsline {paragraph}{Characterization of Queues}{33}
\contentsline {section}{\numberline {3.2}Notably important Queues}{34}
\contentsline {subsection}{\numberline {3.2.1}The $M/M/1$ Queue}{34}
\contentsline {subsection}{\numberline {3.2.2}The $M/G/1$ Queue}{35}
\contentsline {section}{\numberline {3.3}Networks of Queues}{35}
\contentsline {paragraph}{Queueing Networks in general}{35}
\contentsline {paragraph}{Closed Queueing Networks}{36}
\contentsline {chapter}{\numberline {4}Cost Models for Shared Memory Architectures}{39}
\contentsline {section}{\numberline {4.1}Processors-Memory System as Closed Queueing Network}{40}
\contentsline {subsection}{\numberline {4.1.1}Formalization of the Model}{40}
\contentsline {subsection}{\numberline {4.1.2}Performance Analysis of the Model}{42}
\contentsline {section}{\numberline {4.2}Processors-Memory System as Client-Server Model with Request-Reply Behaviour}{44}
\contentsline {subsection}{\numberline {4.2.1}Formalization of the Model}{44}
\contentsline {subsection}{\numberline {4.2.2}Assumptions}{46}
\contentsline {subsection}{\numberline {4.2.3}Model Resolution}{49}
\contentsline {section}{\numberline {4.3}A variant of the Client-Server Model: Heterogeneous Clients}{51}
\contentsline {subsection}{\numberline {4.3.1}Definition}{52}
\contentsline {subsection}{\numberline {4.3.2}Comparison against the Queuing Network Simulator}{52}
\contentsline {subsection}{\numberline {4.3.3}Comments}{58}
\contentsline {section}{\numberline {4.4}Conclusions}{59}
\contentsline {chapter}{\numberline {5}Stochastic Process Algebra Formalization of Client-Server Model}{61}
\contentsline {section}{\numberline {5.1}PEPA: a Process Algebra for Quantitative Analysis}{63}
\contentsline {paragraph}{The Language}{64}
\contentsline {section}{\numberline {5.2}A PEPA Formalism for Client-Server Model with Request-Reply Behaviour}{68}
\contentsline {subsection}{\numberline {5.2.1}Definition}{68}
\contentsline {subsection}{\numberline {5.2.2}Quantitative Comparison with respect to other Resolution Techniques}{70}
\contentsline {paragraph}{Preliminary Considerations}{70}
\contentsline {paragraph}{Model Resolution}{70}
\contentsline {paragraph}{Results}{71}
\contentsline {section}{\numberline {5.3}Conclusion}{74}
\contentsline {chapter}{\numberline {6}Advanced Cost Models: impact of the Parallel Application}{75}
\contentsline {section}{\numberline {6.1}Processes Classes and Processes Phases}{76}
\contentsline {subsection}{\numberline {6.1.1}Classes of Processes}{77}
\contentsline {subsection}{\numberline {6.1.2}Process Phases}{79}
\contentsline {section}{\numberline {6.2}How to deal with more Phases}{81}
\contentsline {section}{\numberline {6.3}Process Phases Modelling}{82}
\contentsline {subsection}{\numberline {6.3.1}Phases by mean of Weighted Average Value}{83}
\contentsline {paragraph}{Comments}{86}
\contentsline {subsection}{\numberline {6.3.2}Explicit Phases}{86}
\contentsline {paragraph}{Results and comments}{88}
\contentsline {subsection}{\numberline {6.3.3}Phases by means of Average Clients}{91}
\contentsline {subsection}{\numberline {6.3.4}Explicit Phases with Average Clients}{92}
\contentsline {paragraph}{Results and comments}{93}
\contentsline {subsection}{\numberline {6.3.5}Comments}{96}
\contentsline {section}{\numberline {6.4}Heterogeneous Clients in PEPA}{96}
\contentsline {subsection}{\numberline {6.4.1}Definition}{97}
\contentsline {subsection}{\numberline {6.4.2}Quantitative Comparison with respect to other Resolution Techniques}{98}
\contentsline {paragraph}{Model Resolution}{98}
\contentsline {paragraph}{Results}{98}
\contentsline {section}{\numberline {6.5}Conclusion}{106}
\contentsline {chapter}{\numberline {7}Advanced Cost Models: Hierarchical Shared Memory}{107}
\contentsline {section}{\numberline {7.1}Hierarchical Client-Server Model with Request-Reply Behaviour}{107}
\contentsline {subsection}{\numberline {7.1.1}Definition}{111}
\contentsline {paragraph}{First Version of Hierarchical Client-Server Model in PEPA}{112}
\contentsline {subparagraph}{Comments}{114}
\contentsline {paragraph}{Second Version of Hierarchical Client-Server Model in PEPA}{114}
\contentsline {subsection}{\numberline {7.1.2}Quantitative Comparison against the Simulation}{115}
\contentsline {paragraph}{Model Resolution}{115}
\contentsline {paragraph}{Results}{116}
\contentsline {section}{\numberline {7.2}Conclusion}{120}
\contentsline {chapter}{\numberline {8}Conclusion and Future Works}{121}
\contentsline {chapter}{References}{124}
